
/**
 * 创建节点
 */
function ListNode(key, val) {
    this.key = key;
    this.val = val;
    this.next = null;
    this.prev = null;
}
/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.capacity = capacity;
    this.count = 0;
    this.hash = {};
    this.dummyHead = new ListNode();
    this.dummyTail = new ListNode();
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.prev = this.dummyHead;
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    let node = this.hash[key];
    if (node) {
        let val = node.val;
        this.moveToHead(node);
        return val;
    } else {
        return -1;
    }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    let node = this.hash[key];
    if (node) {
        node.val = value;
        this.moveToHead(node);
    } else {
        if (this.count === this.capacity) {
            this.delNode();
        }
        node = new ListNode(key, value);
        this.hash[key] = node;
        this.addToHead(node);
    }
};

LRUCache.prototype.moveToHead = function (node) {
    let prev = node.prev;
    let next = node.next;
    prev.next = next;
    next.prev = prev;

    let dummyHeadNext = this.dummyHead.next;
    this.dummyHead.next = node;
    node.prev = this.dummyHead;
    node.next = dummyHeadNext;
    dummyHeadNext.prev = node;
}

//删除最久未使用，也就是链表尾节点
LRUCache.prototype.delNode = function () {
    
    let delNode = this.dummyTail.prev;
    delete this.hash[delNode.key];
    let prev = delNode.prev;
    prev.next = this.dummyTail;
    this.dummyTail.prev = prev;
    this.count--;
}

//新建的节点放入链表头
LRUCache.prototype.addToHead = function (node) {
    let dummyHeadNext = this.dummyHead.next;
    this.dummyHead.next = node;
    node.prev = this.dummyHead;
    node.next = dummyHeadNext;
    dummyHeadNext.prev = node;
    this.count++;
}
